# Q: The sliding window minimum problem takes a list of n numbers and a window
# size k and returns a list of the minimum values in each of the n-k+1
# successive windows. For instance, given the list {4, 3, 2, 1, 5, 7, 6, 8, 9}
# and a window of size 3, the desired output is the list {2, 1, 1, 1, 5, 6, 6}.
# Richard Harter discusses this problem at his blog, along with several
# different solutions.
#
# A: Naive solution is to find the minimum for each window and report. It
# roughly takes O(n^2) time. Another better solution is to use ascending minima
# algorithm which takes O(n) or O(k^2 + nk) to be precise. But since k is
# constant no matter how many n items we are talking, it's still O(n).
#
# Here is how ascending minima works: 
# http://home.tiac.net/~cri/2001/slidingmin.html
#
# The algorithm presented here is the ascending minima algorithm; it requires
# O(n) time and O(k) space. The general idea is to locate the minimum in the
# window, then the minimum in the remainder of the window, and so. Values
# between the ascending minima can be ignored.
# 
# More formally, let W be a vector of values of length k. Define the sequence of
# ascending mimima, A, as follows:
# 
# Let A[0] be the minimum value in W and for j>0 let A[j] be the minimum value
# in W with index greater than the index of A[j-1]. (If two locations have the
# same minimum value take the later one.) Example:
#  
# W = 5,2,8,6,4,7
# A = 2,4,7
# 
# Evidently the length of A is 1 if the minimum in W is the last element in W
# and k if W is monotonic increasing.
# 
# Now suppose that we have a window W on V and that we know the ascending minima
# vector A. Consider what happens when we move the window one location. We add
# one element at the end of the window and remove one element from the beginning
# of the window. Let x be the newly added element. Then A can be updated by
# 
#    1. removing all elements of A greater than or equal to x,
#    2. appending x to A, and
#    3. removing the initial element of A if it is being removed from the window. 
# 
# We do not need to record the window; all we need is the ascending minima
# sequence. However it is necessary to record when an entry in the sequence will
# be deleted from the window. For this reason it is useful if the elements of A
# have two fields, the first being a value from V, i.e., V[i] for some i, and
# the second being the index when the entry will disappear from the window. This
# happens k entries later.
# 
# Since the length of A is bounded and since A is a queue, it is natural to
# store it in a ring buffer.
# 
# Steps (b) and (c) are straightforward without significant alternatives. In
# step (a) we need to locate the last value in A that is less than the newly
# added x. At first sight it might seem that a binary search of A would be
# optimal. This is not the case; the optimal search is from back to front in a
# simple loop.
# 
# The proof is simple enough; the linear search loop deletes elements one by one
# with an O(1) time cost for each deletion. On average the number of deletions
# from A is the same as the number of additions. The upshot is that the average
# time cost of moving the window one location is O(1). 

import random

def naive_sliding_window_minimum(data, size):
   results = []
   maxsize = len(data)
   for i in range(0, maxsize - size + 1):
      curmin = data[i]
      for j in range(i+1, min(i+size, maxsize)):
         if data[j] < curmin:
            curmin = data[j]
      results.append(curmin)
   return results

class AscendingMinima:
   def __init__(self, data, size):
# safe information for use later
      self.minima = []
      self.data = data
      self.size = size
      self.start = 0
      self.stop = size-1

# initialize minima list
      i = 0
      while i < size:
         curmin = self.find_minimum_index(i, size)
         self.minima.append(curmin)
         i = curmin + 1

   def find_minimum_index(self, start, stop):
      curmin = start
      for i in range(start+1, stop):
         if data[i] < data[curmin]:
            curmin = i
      return curmin

   def get_current_min(self):
      return self.data[self.minima[0]]

   def shift_window(self):
# shift the window and return false if it cannot be shifted anymore
      self.start += 1
      self.stop +=1
      if self.stop == len(self.data):
         return False

# if it's okay, then update the minima
      if self.minima[0] < self.start:
         del self.minima[0]
      while self.minima and self.data[self.minima[-1]] > self.data[self.stop]:
         del self.minima[-1]
      self.minima.append(self.stop)
      return True
      
def ascending_minima_sliding_window_mininum(data, size):
   minima = AscendingMinima(data, size)
   results = [minima.get_current_min()]
   while minima.shift_window():
      results.append(minima.get_current_min())
   return results

# now we're ready to find the result
   results = []
   for start in range(0, maxsize - size + 1):
      c1, c2 = which_chunks(start, start+size)
      results.append(min(chunk_mins[c1], chunk_mins[c2]))
   return results


data = list(range(0, 20))
for time in range(0,10):
   random.shuffle(data)
   assert naive_sliding_window_minimum(data, 3) == ascending_minima_sliding_window_mininum(data, 3)

